#!/usr/bin/env python
# -*- coding: utf-8 -*-

# @Time     :2022/04/15
# @Author   :Changshu
# @File     :Exercise124.py

# 124. 二叉树中的最大路径和

class TreeNode:
	def __init__(self,val=0,left=None,right=None):
		self.val=val
		self.left=left
		self.right=right


class Solution:
	def __init__(self):
		self.maxSum=float('-inf')

	def maxPathSum(self,root:TreeNode)->int:
		def maxGain(node:TreeNode):
			if not node:
				return 0

			# 和0比大小很关键，淘汰非0的数
			leftGain=max(maxGain(node.left),0)
			rightGain = max(maxGain(node.right), 0)

			maxNewPath=node.val+leftGain+rightGain
			self.maxSum=max(self.maxSum,maxNewPath)

			return node.val+max(leftGain,rightGain)

		maxGain(root)
		return self.maxSum


if __name__ == '__main__':
	node1=TreeNode(4)
	node2=TreeNode(5)
	node3=TreeNode(2)
	node4 = TreeNode(-1)
	node5 = TreeNode(-3)

	node1.left=node2
	node1.right=node3

	node3.left=node4
	node3.right=node5
	s=Solution()
	print(s.maxPathSum(node1))